package com.example.demo.arithmetic.datastructure.tree;

// 递归实现前中后序遍历
public class TreeTraversal {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(
                new TreeNode(new TreeNode(4), 2, null),
                1,
                new TreeNode(new TreeNode(5), 3, new TreeNode(6)));
        System.out.println("前序");
        preOrder(root);
        System.out.println("\n中序");
        inOrder(root);
        System.out.println("\n后序");
        postOrder(root);

    }


    /**
     * 前序遍历 root->左->右
     *
     * @param node
     */
    static void preOrder(TreeNode node) {
        System.out.print(node.val + "\t");
        if (node.left != null) {
            preOrder(node.left);
        }
        if (node.right != null) {
            preOrder(node.right);
        }
    }


    /**
     * 中序遍历 左->root->右
     *
     * @param node
     */
    static void inOrder(TreeNode node) {

        if (node.left != null) {
            inOrder(node.left);
        }
        System.out.print(node.val + "\t");
        if (node.right != null) {
            inOrder(node.right);
        }
    }

    /**
     * 中序遍历 左->root->右
     *
     * @param node
     */
    static void postOrder(TreeNode node) {

        if (node.left != null) {
            postOrder(node.left);
        }
        if (node.right != null) {
            postOrder(node.right);
        }
        System.out.print(node.val + "\t");
    }
}


